package com.graph;

import java.util.LinkedList;

public class Solution1162 {
    public int maxDistance(int[][] grid) {
        LinkedList<int[]> queue = new LinkedList<>();
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) queue.add(new int[]{i, j});
            }
        }
        if (queue.size() == 0 || queue.size() == grid.length * grid[0].length) return -1;
        int[] cur = null;
        while (!queue.isEmpty()) {
            cur = queue.removeFirst();
            int i = cur[0];
            int j = cur[1];
            if (i - 1 >= 0 && grid[i - 1][j] == 0) {
                grid[i - 1][j] = grid[i][j] + 1;
                queue.add(new int[]{i - 1, j});
            }
            if (j - 1 >= 0 && grid[i][j - 1] == 0) {
                grid[i][j - 1] = grid[i][j] + 1;
                queue.add(new int[]{i, j - 1});
            }
            if (i + 1 <= grid.length - 1 && grid[i + 1][j] == 0) {
                grid[i + 1][j] = grid[i][j] + 1;
                queue.add(new int[]{i + 1, j});
            }
            if (j + 1 <= grid[0].length - 1 && grid[i][j + 1] == 0) {
                grid[i][j + 1] = grid[i][j] + 1;
                queue.add(new int[]{i, j + 1});
            }

        }
        return grid[cur[0]][cur[1]] - 1;
    }
}
